#include <iostream>
#include <vector>

namespace test
{
template<class T>
struct less
{
    bool operator()(const T& x, const T& y)
    {
        return x < y;
    }
};

template<class T>
struct greater
{
    bool operator()(const T& x, const T& y)
    {
        return x > y;
    }
};

template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue
{
public:
    void adjust_up(int child)
    {
        int parent = (child - 1) / 2;

        while (child > 0)
        {
            if (_cmp(_con[parent], _con[child]))
                swap(_con[parent], _con[child]);
            else
                break;

            child = parent;
            parent = (child - 1) / 2;
        }
    }

    void adjust_down(int parent)
    {
        int child = parent * 2 + 1;

        while (child < _con.size())
        {
            if (child + 1 < _con.size() && _cmp(_con[child], _con[child + 1]))
                child++;

            if (_cmp(_con[parent], _con[child]))
                swap(_con[parent], _con[child]);
            else
                break;

            parent = child;
            child  = parent * 2 + 1;
        }
    }

    void push(const T& x)
    {
        _con.push_back(x);
        adjust_up(_con.size() - 1);
    }

    void pop()
    {
        _con[0] = _con[_con.size() - 1];
        _con.pop_back();
        adjust_down(0);
    }

    size_t size()
    {
        return _con.size();
    }

    bool empty()
    {
        return _con.empty();
    }

    T& top()
    {
        return _con[0];
    }

private:
    Container _con;
    Compare _cmp;
};

}